package com.cqs.leetcode.math;

import com.cqs.leetcode.ds.ArraysUtils;
import com.sun.deploy.util.ArrayUtil;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

/**
 * lixw
 * 2021/11/3
 **/
public class TrappingRainWaterII407 {

    private class Point {
        int x = 0;
        int y = 0;
        int weight = 0;

        public Point(int x, int y, int weight) {
            this.x = x;
            this.y = y;
            this.weight = weight;
        }
    }

    public int trapRainWater(int[][] heightMap) {
        int m = heightMap.length;
        int n = heightMap[0].length;
        PriorityQueue<Point> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o.weight));
        boolean[][] visited = new boolean[m][n];
        //行
        for (int i = 0; i < n; i++) {
            queue.add(new Point(0, i, heightMap[0][i]));
            queue.add(new Point(m - 1, i, heightMap[m - 1][i]));
            visited[0][i] = true;
            visited[m - 1][i] = true;
        }
        //列
        for (int i = 1; i < m - 1; i++) {
            queue.add(new Point(i, 0, heightMap[i][0]));
            queue.add(new Point(i, n - 1, heightMap[i][n - 1]));
            visited[i][0] = true;
            visited[i][n - 1] = true;
        }

        int vol = 0;
        while (queue.size() > 0) {
            //找到最小的高度的边界
            Point point = queue.poll();
            if (point.x > 0 && !visited[point.x - 1][point.y]) {
                visited[point.x - 1][point.y] = true;
                int val = Math.max(heightMap[point.x - 1][point.y], point.weight);
                vol += val - heightMap[point.x - 1][point.y];
                queue.add(new Point(point.x - 1, point.y, val));
                ///continue;
            }
            //下
            if (point.x + 1 < m && !visited[point.x + 1][point.y]) {
                visited[point.x + 1][point.y] = true;
                int val = Math.max(heightMap[point.x + 1][point.y], point.weight);
                vol += val - heightMap[point.x + 1][point.y];
                queue.add(new Point(point.x + 1, point.y, val));
                //continue;
            }
            //左
            if (point.y > 0 && !visited[point.x][point.y - 1]) {
                visited[point.x][point.y - 1] = true;
                int val = Math.max(heightMap[point.x][point.y - 1], point.weight);
                vol += val - heightMap[point.x][point.y - 1];
                queue.add(new Point(point.x, point.y - 1, val));
                ///continue;
            }
            //右
            if (point.y + 1 < n && !visited[point.x][point.y + 1]) {
                visited[point.x][point.y + 1] = true;
                int val = Math.max(heightMap[point.x][point.y + 1], point.weight);
                vol += val - heightMap[point.x][point.y + 1];
                queue.add(new Point(point.x, point.y + 1, val));
            }
        }
        return vol;
    }

    public static void main(String[] args) {
        List<int[][]> cases = new ArrayList<>();
        TrappingRainWaterII407 t = new TrappingRainWaterII407();
        //115
        cases.add(new int[][]{{9, 9, 9, 9, 9, 9, 8, 9, 9, 9, 9}, {9, 0, 0, 0, 0, 0, 1, 0, 0, 0, 9}, {9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9}, {9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9}, {9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9}});
        for (int[][] c : cases) {
            int val = t.trapRainWater(c);
            StringBuilder s = new StringBuilder();
            for (int j = 0; j < c.length; j++) {
                s.append(ArraysUtils.formatInts(c[j]));
            }
            System.out.println(s.toString() + "--->" + val);
        }

    }
}
